type cenv = list<string>

let rec index = (l: list<'a>, v: 'a, n: int) => {
  switch (l, n) {
  | (list{x, ...rest}, 0) =>
    if x == v {
      0
    } else {
      1 + index(rest, v, 0)
    }
  | (list{x, ...rest}, n) =>
    if x == v {
      1 + index(rest, v, n - 1)
    } else {
      1 + index(rest, v, n)
    }
  | (list{}, _) => 0
  }
}

let rec comp = (expr: Interpreter.expr, cenv: cenv): Nameless.expr => {
  switch expr {
  | Cst(i) => Cst(i)
  | Add(a, b) => Add(comp(a, cenv), comp(b, cenv))
  | Mul(a, b) => Mul(comp(a, cenv), comp(b, cenv))
  | Var(x) => Var(cenv->index(x, 0))
  | Let(x, e1, e2) => Let(comp(e1, cenv), comp(e2, list{x, ...cenv}))
  }
}

type sv = Slocal | Stmp
type senv = list<sv>

let compile = expr => {
  let rec go = (expr: Nameless.expr, senv: senv): list<Stack.instr> => {
    switch expr {
    | Cst(i) => list{Cst(i)}
    | Var(s) => list{Var(index(senv, Slocal, s))}
    | Add(e1, e2) => List.concatMany([go(e1, senv), go(e2, list{Stmp, ...senv}), list{Add}])
    | Mul(e1, e2) => List.concatMany([go(e1, senv), go(e2, list{Stmp, ...senv}), list{Mul}])
    | Let(e1, e2) => List.concatMany([go(e1, senv), go(e2, list{Slocal, ...senv}), list{Swap, Pop}])
    }
  }
  go(expr, list{})
}

module SinglePass = {
  type sv = Slocal(string) | Stmp
  type senv = list<sv>
  let compile = expr => {
    let rec go = (expr: Interpreter.expr, senv: senv): list<Stack.instr> => {
      switch expr {
      | Cst(i) => list{Cst(i)}
      | Var(s) => list{Var(index(senv, Slocal(s), 0))}
      | Add(e1, e2) => List.concatMany([go(e1, senv), go(e2, list{Stmp, ...senv}), list{Add}])
      | Mul(e1, e2) => List.concatMany([go(e1, senv), go(e2, list{Stmp, ...senv}), list{Mul}])
      | Let(x, e1, e2) =>
        List.concatMany([go(e1, senv), go(e2, list{Slocal(x), ...senv}), list{Swap, Pop}])
      }
    }
    go(expr, list{})
  }
}
